# coding: utf-8
# LIFO栈实现
# python的list可以快速实现stack
#stack的4个关键操作：push、pop、top、isEmpty
# https://www.cnblogs.com/dbf-/p/11277874.html

import random

class MyStack(object):
    def __init__(self):
        self.data=[]
    def __repr__(self):
        return "MyStack {0}".format(self.data)
    def push(self,e):
        self.data.append(e)
    def pop(self):
        #list.pop()没有传参默认移除最后一位，即lst[-1]；有传参，移除指定位置，相当于remove
        if len(self.data)<=0:
            return
        return self.data.pop()
    def top(self):
        return self.data[-1]
    def isEmpty(self):
        return self.data==[]

class MyStack2(object):
    def __init__(self, maxSize):
        #固定长度数组
        self.data=[0 for _ in range(maxSize)]
        #栈顶指针
        self.topPos=-1
    def __repr__(self):
        return "MyStack {0}".format(self.data)
    def push(self,e):
        if self.topPos>=len(self.data)-1:
            raise Exception("越界了")
        self.topPos+=1
        self.data[self.topPos]=e
    def pop(self):
        if self.topPos<=-1:
            raise Exception("越界了")
        e=self.data[self.topPos]
        self.topPos-=1
        return e
    def top(self):
        return self.data[self.topPos]
    def isEmpty(self):
        return self.topPos==-1

#使用栈检查括号
def checkParens(inputStr):
    leftParens="([{"
    rightParens=")]}"
    parensDict={"(":")", "[":"]", "{":"}"}
    st=MyStack()
    for ch in inputStr:
        if ch==" ":
            continue
        if ch in leftParens:
            st.push(ch)
        if ch in rightParens:
            if st.isEmpty():
                return False
            if parensDict[st.top()]!=ch:
                return False
            #括号匹配，弹出
            st.pop()
    #栈为空，说明匹配完全
    return st.isEmpty()

#使用栈记录迷宫路径
#迷宫(0表示可以通过，1表示不能通过，-1表示已走过，最外一层是城墙，起点是[1][1]，终点shi[8][8])
maze=[
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
    [1, 0, 0, 0, 0, 1, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
    [1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
    [1, 0, 1, 0, 0, 0, 1, 0, 0, 1],
    [1, 0, 1, 1, 1, 0, 1, 1, 0, 1],
    [1, 1, 0, 0, 0, 0, 0, 1, 0, 1],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
]
#4个方向，返回一个Tuple
directions=[
    lambda x,y:(x-1,y),
    lambda x,y:(x+1,y),
    lambda x,y:(x,y-1),
    lambda x,y:(x,y+1)
]

#dfs对应栈（dfs找到的不一定是最短路径）
#for...break...else
def findPath(x1,y1,x2,y2):
    st=MyStack()
    maze[x1][y1]=-1
    st.push((x1,y1))

    #stack不为空表示还有退路
    while not st.isEmpty():
        #取最新的一个节点
        curPos=st.top()
        if curPos[0]==x2 and curPos[1]==y2:
            print(st)
            return True
        #打乱方向
        random.shuffle(directions)
        #python独特的for...break...else 遍历成功或失败 语句
        for direct in directions:
            nextPos=direct(curPos[0],curPos[1])
            #如果可以走且未走过
            if maze[nextPos[0]][nextPos[1]] == 0:
                st.push(nextPos)
                #标记为已走过
                maze[nextPos[0]][nextPos[1]]=-1
                #遍历成功
                break
        #遍历失败
        else:
            #撤出这个节点
            st.pop()
    print("找不到出口")
    return False

s1=MyStack2(10)
s1.push(1)
s1.push(2)
s1.push(3)
print("stack:",s1)
print("top:",s1.top())
print(s1.pop())
print(s1.pop())
print(s1.pop())
print("isEmpty:",s1.isEmpty())

print("checkParens1:",checkParens('{[()]}()[{()}]'))

findPath(1,1,8,8)
